import java.util.ArrayList;
import java.util.Hashtable;


public class TerminalStateIdentifier
{

	
	private Hashtable<String, State[]> transitionTable ;
	private Hashtable<String, Integer> ruleTwoTable ;
	private int childrenNum ;
	private Node root ;
	private ArrayList<State> states ;
	
	
	/**
	 * The Constructor 
	 * @param transTable : Two Dimensional array of Strings
	 *                     Representing the Transition Table
	 */
	
	public TerminalStateIdentifier(String[][] transTable)
	{
		transitionTable = new Hashtable<String, State[]>();
		ruleTwoTable = new Hashtable<String, Integer>();
		int rowLength = transTable[0].length;
		int nextStatesNum = (rowLength-1)/2;
		childrenNum = nextStatesNum;
		ArrayList<State> rootValue = new ArrayList<State>();
		for(int i = 0 ; i < transTable.length ; i++)
		{
			State[] currentState = new State[nextStatesNum];
			for(int j = 0 ; j < nextStatesNum ; j++)
			{
				currentState[j]= new State(transTable[i][2*j+1],transTable[i][2*j+2]);
			}
            transitionTable.put(transTable[i][0], currentState);
            rootValue.add(new State(transTable[i][0],""));
		}
		root = new Node();
		root.setParent(null);
		root.setValue(rootValue);
		root.setInput("");
		root.setChildren(new Node[childrenNum]);
		ruleTwoTable.put(tohashString(root), 1);
	}
	
	
	/**
	 * @return the transitionTable
	 */
	public Hashtable<String, State[]> getTransitionTable()
	{
		return transitionTable;
	}


	/**
	 * @param transitionTable the transitionTable to set
	 */
	public void setTransitionTable(Hashtable<String, State[]> transitionTable)
	{
		this.transitionTable = transitionTable;
	}

	/**
	 * Method to get the next node of a given node according to a given input 
	 * @param currentNode : the current node
	 * @param input : the input
	 * @return : the next node
	 */
    private Node getNextNode(Node currentNode,int input)
    {
    	ArrayList<State> currentList =  currentNode.getValue();
    	ArrayList<State> nextNodeList = new ArrayList<State>();
    	Hashtable<String, Integer> auxTable = new Hashtable<String, Integer>(currentList.size()*2) ;
    	
    	for(int i = 0 ; i < currentList.size() ; i++)
    	{
    		State currentState = currentList.get(i);
    		State temp = transitionTable.get(currentState.getState())[input];
    		State nextState = new State(temp.getState(),currentState.getOutPut()+temp.getOutPut());
    		
    		if(auxTable.get(nextState.toString())==null)
    		{
    		auxTable.put(nextState.toString(), 1);	
    		nextNodeList.add(nextState);
    		}
    	}
    	
    	Node nextNode = new Node();
    	nextNode.setValue(nextNodeList);
		return nextNode;	
    }
    /**
     * Method to get the hash value of the node that would be put in 
     * the ruleTwoTable 
     * @param node : the node to be hashed
     * @return the hash string of the node
     */
	
	private String tohashString(Node node)
	{
		ArrayList<State> list = node.getValue();
		int isDone = 1 ;
		for(int i = 0 ; i < list.size() ; i++)
		{
			for (int j = i+1 ; j < list.size() ; j++)
			{
				if(list.get(i).getOutPut().equals(list.get(j).getOutPut()))
				{
					isDone = 0 ;
					break ;
				}
			}
		}
		Hashtable<String, ArrayList<String>> auxTable = new Hashtable<String, ArrayList<String>>(list.size()*2) ;
		ArrayList<String> keys = new ArrayList<String>();
		for(int i = 0 ; i < list.size() ; i++)
		{
			String key = list.get(i).getOutPut();
			String value = list.get(i).getState();
			if(!auxTable.containsKey(key))
			{
				ArrayList<String> temp = new ArrayList<String>();
				temp.add(value);
				auxTable.put(key, temp);
				keys.add(key);
			}
			else
			{
				ArrayList<String> temp = auxTable.get(key);
				auxTable.remove(key);
				boolean isAdded = false ;
				for(int k = 0 ; k < temp.size() ; k++)
				{
					String s = temp.get(k);
					if((s.compareTo(value)>0))
					{
						temp.add(k, value);
						isAdded = true ;
						break;
					}
				}
				if(!isAdded)
				{
					temp.add(value);
				}
				auxTable.put(key, temp);
			}
		}
		ArrayList<String> result = new ArrayList<String>();
		for(int i = 0 ; i < keys.size() ; i++)
		{
			String s = "";
			ArrayList<String> temp = auxTable.get(keys.get(i));
			for(int x=0 ; x <temp.size();x++)
			{
				s+=temp.get(x);
			}
			boolean isAdded = false ;
			for(int n = 0 ; n < result.size() ; n++)
			{
				if(s.compareTo(result.get(n))>0)
				{
					result.add(n, s);
					isAdded = true ;
					break;
				}
			}
			if(!isAdded)
			{
				result.add(s);
			}
		}
		String finalResult = "$";
		for(int x=0 ; x <result.size();x++)
		{
			finalResult+= result.get(x)+"$";
		}
	
		return finalResult+isDone;
	}
	
	/**
	 * Method to find all possible homing sequences for the given transition table
	 * and print them 
	 */
	
	public String findAllHomingSequences()
	{
		ArrayList<Node> nodes = new ArrayList<Node>();
		nodes.add(root);
		String result = "";
		boolean isDone =false;
		do
		{
			int size = nodes.size();
			for(int i = 0 ; i < size ; i++)
			{
				Node currentNode = nodes.get(0);
				nodes.remove(0);
				for(int j = 0 ; j < childrenNum ; j++)
				{
					Node temp = getNextNode(currentNode, j);
					currentNode.getChildren()[j]= temp;
					temp.setParent(currentNode);
					temp.setInput(""+j);
					temp.setChildren(new Node[childrenNum]);
					String hashString = tohashString(temp);
					// Test Rule 1
					if(hashString.charAt(hashString.length()-1)=='1')
					{
						result+=("For Input Sequence :"+getSequence(temp))+"\n";
						result+=("State/Output pairs are:\n");
						result+=temp.toString();
						result+=("-------------------------\n");
						isDone = true ;
					}
					// Test Rule 2
					else if(!ruleTwoTable.containsKey(hashString))
					{
						ruleTwoTable.put(hashString, 1);
						nodes.add(temp);
					}
				}
			}
		}
		while(nodes.size()>0);
		if(!isDone)
		{
			result+=("No homing Sequences found");
		}
		return result;
	}
	
	/**
	 * Method to get the input sequence resulted in the
	 * given terminal node
	 * @param node : the node to get the input sequence resulted in it .
	 * @return : the input sequence wanted
	 */
	
	private String getSequence(Node node)
	{
		Node current = node ;
		String result = "";
		while(current != null)
		{
			result=current.getInput()+result;
			current = current.getParent();
		}
		return result ;
	}
	
	/**
	 * Method to find the homing sequences 
	 * @param shortestSequences : if true --> find the shortest sequences , else find all sequences
	 */
	public void findHomingSequences(boolean shortestSequences)
	{
		if(shortestSequences)
		{
			findShortestHomingSequences();
		}
		else
		{
			findAllHomingSequences();
		}
	}
	
	public String findShortestHomingSequences()
	{
		String result ="";
		ArrayList<Node> nodes = new ArrayList<Node>();
		nodes.add(root);
		boolean isDone = false ;
		do
		{
			int size = nodes.size();
			for(int i = 0 ; i < size ; i++)
			{
				Node currentNode = nodes.get(0);
				nodes.remove(0);
				for(int j = 0 ; j < childrenNum ; j++)
				{
					Node temp = getNextNode(currentNode, j);
					currentNode.getChildren()[j]= temp;
					temp.setParent(currentNode);
					temp.setInput(""+j);
					temp.setChildren(new Node[childrenNum]);
					String hashString = tohashString(temp);
					// Test Rule 1
					if(hashString.charAt(hashString.length()-1)=='1')
					{
						result+=("For Input Sequence :"+getSequence(temp))+"\n";
						result+=("State/Output pairs are:\n");
						result+=temp.toString();
						result+=("-------------------------\n");
						states = temp.getValue();
						isDone = true ;
					}
					// Test Rule 2
					else if(!ruleTwoTable.containsKey(hashString))
					{
						ruleTwoTable.put(hashString, 1);
						nodes.add(temp);
					}
				}
			}
		}
		while(nodes.size()>0 && !isDone);	
		
		if(!isDone)
		{
			result+=("No homing Sequences found");
		}
		return result;
	}


	public String findSynchronizingSequences()
	{
		ArrayList<Node> nodes = new ArrayList<Node>();
		nodes.add(root);
		String result="";
		boolean isDone = false ;
		do
		{
			int size = nodes.size();
			for(int i = 0 ; i < size ; i++)
			{
				Node currentNode = nodes.get(0);
				nodes.remove(0);
				for(int j = 0 ; j < childrenNum ; j++)
				{
					Node temp = getNextNode(currentNode, j);
					currentNode.getChildren()[j]= temp;
					temp.setParent(currentNode);
					temp.setInput(""+j);
					temp.setChildren(new Node[childrenNum]);
					String hashString = tohashString(temp);
					// Test Rule 1
					if(temp.getValue().size()==1)
					{
						result+=("For Synchronizing Input Sequence :"+getSequence(temp)+"\n");
						result+=("State achieved is :"+"\n");
						result+=(temp.getValue().get(0).getState().substring(0, temp.getValue().get(0).getState().length())+"\n");
						result+=("-------------------------\n");
						states = temp.getValue();
						isDone = true ;
					}
					// Test Rule 2
					else if(!ruleTwoTable.containsKey(hashString))
					{
						ruleTwoTable.put(hashString, 1);
						nodes.add(temp);
					}
				}
			}
		}
		while(nodes.size()>0);
		if(!isDone)
		{
			result+=("The Tree is not Synchronizing\n");
			result+=("------------------------");
		}
		return result;
	}
	
	public  ArrayList<State> getStates()
	{
		return states;
	}
	public static void main(String[] args)
	{
		String[][] table = {{"A","B","","D",""},
							{"B","A","","B",""},
							{"C","D","","A",""},
							{"D","D","","C",""}};

		String[][] table2 =    {{"A","C","I0","E","I0"},
								{"B","A","I1","D","I0"},
								{"C","E","I0","D","I0"},
								{"D","F","I1","A","I0"},
								{"E","B","I2","F","I0"},
								{"F","B","I0","C","I0"}};

		
		
		TerminalStateIdentifier t = new TerminalStateIdentifier(table);
		System.out.println(t.findSynchronizingSequences());
		
//		TerminalStateIdentifier t2 = new TerminalStateIdentifier(table2);
//		System.out.println(t2.findAllHomingSequences());		
//		

	}

}
